codeforces 254B

ACM
评论

给出n项任务，每项任务有需要的人数，需要花费时间，截至时间 这些属性，问至少需要多少人才能把这些活干完。挺水的。

注意开始日期可能在头一年。这不是个闰年，并且时间下界不会到头一年的2月，先处理截止日期，再在整个工作时间内的每一天的需要总人数都加上这项工作需要的人数，最后找最大值。听上去用线段树维护最大值也可以是很有前途的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<numeric>
#include<set>
#pragma comment(linker, "/STACK:10240000000,10240000000")
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define inf 0x3f3f3f3f
#define debug puts("-----")
#define maxn 50000+4
#define uLL unsigned long long
#define LL long long
int day[700];
int mo[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
	freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	int n;
	scanf("%d",&n);
	int m,d,p,t;
	mem(day,0);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&m,&d,&p,&t);
		int date=0;
		for(int j=0;j<m;j++)
			date+=mo[j];
		date+=d;
		date+=150;
		int st=date-t;
		int cnt=0;
		for(;st<date;st++)
			day[st]+=p;
		//printf("%d\n",cnt);
	}
	int ans=0;
	for(int i=0;i<700;i++)
		ans=max(ans,day[i]);
	printf("%d\n",ans);	
}

EOF